             /*

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

class PalindromeList {
public:
    ListNode* findcenternode(ListNode* phead)
    {
        ListNode* fast=phead;
        ListNode* slow=phead;
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
    ListNode* reverseList(ListNode* phead)
    {
        ListNode* n1,*n2,*n3;
        n1=NULL;
        n2=phead;
        n3=n2->next;
        while(n2)
        {
             n2->next=n1;
             n1=n2;
             n2=n3;
             if(n3)
            {
               n3=n3->next;
            }
        }
        return n1;
    }
    bool chkPalindrome(ListNode* A) {
       //找中间结点
        ListNode* mid=findcenternode(A);
        
        //反转中间结点之后的链表
        ListNode* right=reverseList(mid);

        //从原链表和反转链表比较结点值
        ListNode* left=A;
        while(right)
        {
            if(left->val!=right->val)
            {
                return false;
            }
            left=left->next;
            right=right->next;
        }
        return true;
    }
};